#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct LinkList
{
    ElemType val;
    struct LinkList *next;
} ListNode;

void InitList(ListNode *&head) //初始化单链表
{
    head = (LinkList *)malloc(sizeof(ListNode));
    head->next = NULL;
}

void CreateListR(ListNode *&L, ElemType a[], int n) //尾插法插入
{
    ListNode *r = L, *s;
    for (int i = 0; i < n; i++)
    {
        s = (ListNode *)malloc(sizeof(ListNode));
        s->val = a[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;
}

void OutList(ListNode *L) //输出链表
{
    ListNode *p = L->next;
    while (p != NULL)
    {
        printf("%c ", p->val);
        p = p->next;
    }
    printf("\n");
}

int ListLength(ListNode *L) //求单链表长度
{
    int len = 0;
    ListNode *p = L;
    while (p->next != NULL)
    {
        len++;
        p = p->next;
    }
    return len;
}

bool ListEmpty(ListNode *L) //判断单链表是否为空
{
    return L->next == NULL;
}

bool GetElem(ListNode* L, int num, char& e) //返回第num个元素的值
 {
 	if(num<=0)  return false;
    ListNode* p = L;
    int count = 0;

    while (p != NULL) {
        
        if (count == num)
		{
            e = p->val;
            return true;
        }
        count++;
        p = p->next;
    }
    return false;
}

int LocateElem(ListNode *L, ElemType e) //输出元素e的位置
{
    int num = 1;
    ListNode *p = L->next;
    while (p != NULL && p->val != e)
    {
        p = p->next;
        num++;
    }
    if (p == NULL)
        return -1;
    else
        return num;
}

bool ListInsert(ListNode *&L, int num, ElemType e) //在指定位置插入元素
{
    int i = 0;
    ListNode *p = L, *s;
    if (num <= 0)
        return false;
    while (i < num - 1 && p != NULL)
    {
        i++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else
    {
        s = (ListNode *)malloc(sizeof(ListNode));
        s->val = e;
        s->next = p->next;
        p->next = s;
        return true;
    }
}

bool DeleteList(ListNode *&L, int num, ElemType &e) //删除单链表的第num个元素
{
    int i = 0;
    ListNode *p = L, *r;
    if (num <= 0)
        return false;
    while (i < num - 1 && p != NULL)
    {
        i++;
        p = p->next;
    }
    if (p == NULL)
        return false;
    else
    {
        r = p->next;
        if (r == NULL)
            return false;
        e = r->val;
        p->next = r->next;
        free(r);
        return true;
    }
}

void DestoryList(ListNode *&L) //释放单链表
{
    ListNode *pre = L, *p = L->next;
    while (p != NULL)
    {
        free(pre);
        pre = p;
        p = pre->next;
    }
    free(pre);
}
